<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<script>
    class MinHeap {
        constructor() {
            this.data = [];
        }
        compare(a,b){
            return a - b;
        }
        insert(val){
            this.data.push(val);
            this.shiftUp();
        }
        size(){
            return this.data.length;
        }
        deleteMin(){
            if(this.size()){
                let res = this.data[0];
                if(this.size() > 1){
                    this.shiftDown();
                }else{
                    this.data = [];
                }
                return res;
            }else {
                return null;
            }
        }
        peek(){
            if(this.size()){
                return this.data[0]
            }else {
                return null;
            }
        }
        shiftUp(){
            let child_index = this.data.length - 1;//>0
            let parent_index = null;//>= 0
            while (child_index > 0){
                parent_index = (child_index -1)/2;
                if(this.compare(this.data[child_index],this.data[parent_index]) < 0){
                    this.swap(child_index,parent_index);
                    child_index = parent_index;
                }else {
                    break;
                }
            }
        }
        shiftDown(){
            this.data[0] = this.data[this.size() - 1];
            this.data.pop();
            let min_index = 0;
            let left_index = 2 * min_index + 1;
            let right_index = 2 * min_index + 2;
            let temp = null;
            debugger
            while (left_index < this.size()){
                if(right_index < this.size()){
                    if(this.compare(this.data[left_index],this.data[right_index]) < 0){
                        temp = left_index;
                    }else {
                        temp = right_index;
                    }
                }else{
                    temp = left_index;
                }
                if(this.compare(this.data[min_index],this.data[temp]) > 0){
                    this.swap(min_index,temp);
                    min_index = temp;
                }
            }
        }
        swap(i,j){
            [this.data[i],this.data[j]] = [this.data[j],this.data[i]]
        }
    }
    let min_heap = new MinHeap();
    for (let num of [4, 5, 8, 2]) {
        min_heap.insert(num);
    }

    console.log(min_heap)
    console.log(min_heap.size())
    min_heap.deleteMin();
    console.log(min_heap)
    /*[4, 5, 8, 2]*/


</script>
</html>
